const numArr = new Array(Math.floor(10 + Math.random() * 10)).fill(null).map(() => Math.floor(Math.random() * 100))
// const numArr = [1, 2]
// const numArr = new Array(1000).fill(null).map((_index, index, arr) => arr.length - index)
console.log(numArr)
let time = 0

/**
 * 数组排序
 * @param {Array} arr 数组
 * @param {Number} start 
 * @param {Number} end 
 * @returns 
 */
const sort = (arr) => {
    if (arr.length <= 1)  return arr
    let start = 0
    let end = arr.length - 1
    let baseNum = arr[start]
    const newArr = []
    if (start < end) {
        start++
        while (start < end) {
            time++
            if (arr[end] < baseNum) {
                if (arr[start] > baseNum) [arr[end], arr[start]] = [arr[start], arr[end]]
                else start++
            } else end--
        }
        if (arr[0] > arr[start]) [arr[0], arr[start]] = [arr[start], arr[0]]
        const leftArr = sort(arr.slice(0, start))
        const rightArr = sort(arr.slice(start))
        newArr.push(...leftArr)
        newArr.push(...rightArr)
    } else {
        if (start == end) [arr[0], arr[start]] = [arr[start], arr[0]]
        newArr.concat(arr)
    }
    return newArr
}
const newArr = sort(numArr)
console.log('endArr: ',newArr)
console.log('time: ', time);
